/**
 * Copyright (c) 2009-2011, chunquedong(YangJiandong)
 * 
 * This file is part of ChunMap project
 * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE(Version >=3)
 * 
 * History:
 *     2010-05-05  Jed Young  Creation
 */
package chunmap.data.index;

import java.util.ArrayList;
import java.util.List;

import chunmap.data.feature.Feature;
import chunmap.data.feature.VisitAction;
import chunmap.data.feature.VisitFunc;
import chunmap.model.coord.Position;
import chunmap.model.elem.Envelope;

public class QuartNode {
	private List<Feature> list;
    private int deep;
    private int maxDeep;
    private boolean isLeaf = true;
    private Envelope envelope;
    /*
       2 | 3
       --+--
       0 | 1
    */
    QuartNode[] subNode;

    public QuartNode(Envelope envelope, int deep, int maxDeep)
    {
        this.envelope = envelope;
        this.deep = deep;
        this.maxDeep = maxDeep;
    }

    public Envelope getEnvelope() { return envelope; }
    //------------------------------------------------------------------------

    public void insert(Feature f)
    {
        if(!envelope.hasIntersect(f.getEnvelop()))return;
        if (isLeaf)
        {
            if (list == null)
            {
                list = new ArrayList<Feature>();
                list.add(f);
                return;
            }

            if (deep < maxDeep && list.size() > 4)
            {
                createLeaf();
                fillDataToSubNode();
                insertToSubNode(f);
                return;
            }

            list.add(f);
        }
        else
        {
            insertToSubNode(f);
        }
    }
    private void createLeaf()
    {
        subNode = new QuartNode[4];
        Position p=envelope.getCenter();

        Envelope env;
        env=new Envelope(envelope.getMinPoint(),p);
        subNode[0] = new QuartNode(env, deep + 1, maxDeep);

        env = new Envelope(envelope.rightDown(), p);
        subNode[1] = new QuartNode(env, deep + 1, maxDeep);

        env = new Envelope(envelope.leftUp(), p);
        subNode[2] = new QuartNode(env, deep + 1, maxDeep);

        env = new Envelope(envelope.getMaxPoint(), p);
        subNode[3] = new QuartNode(env, deep + 1, maxDeep);
    }

    private void fillDataToSubNode()
    {
        for (Feature f : list)
        {
            insertToSubNode(f);
        }
        isLeaf = false;
        list = null;
    }
    private void insertToSubNode(Feature f)
    {
        for (int i = 0; i < 4; i++)
        {
            subNode[i].insert(f);
        }
    }

    public boolean remove(Feature f)
    {
        if (!envelope.hasIntersect(f.getEnvelop())) return false;
        if (isLeaf)
        {
            if (list == null) return false;

            return list.remove(f);
        }
        else
        {
            boolean isRemove = false;
            for (int i = 0; i < 4; i++)
            {
                if (subNode[i].remove(f))
                {
                    isRemove = true;
                }
            }
            return isRemove;
        }
    }

    //------------------------------------------------------------------------

    public void select(Envelope envelope, VisitAction filter)
    {
        if (isLeaf)
        {
            if (list == null) return;
            for (Feature f : list)
            {
                filter.execute(f);
            }
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                subNode[i].select(envelope, filter);
            }
        }
    }
    public void search(Envelope envelope, VisitFunc filter)
    {
        if (isLeaf)
        {
            if (list == null) return;
            for (Feature f : list)
            {
                if (!filter.execute(f)) break;
            }
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                subNode[i].search(envelope, filter);
            }
        }
    }

    public void find(VisitFunc filter)
    {
        if (isLeaf)
        {
            if (list == null) return;
            for (Feature f : list)
            {
                if (!filter.execute(f)) break;
            }
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                subNode[i].find(filter);
            }
        }
    }
    public void each(VisitAction filter)
    {
        if (isLeaf)
        {
            if (list == null) return;
            for (Feature f : list)
            {
                filter.execute(f);
            }
        }
        else
        {
            for (int i = 0; i < 4; i++)
            {
                subNode[i].each(filter);
            }
        }
    }
}